public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();
        String[] strs = new String[]{"10","0","1"};
        System.out.println(test.findMaxForm(strs, 1, 1));
    }

    public int findMaxForm(String[] strs, int m, int n) {
        /**
         * 一和零
         * 状态表示：
         *  dp[i][j][k]表示在前i个元素中进行挑选，使得0的个数不超过j 1的个数不超过k，此时最大的子集长度
         * 状态转移方程：
         *
         * 初始化：
         *
         * 返回值：
         *  return dp[len][m][n];
         * */
        // 1 预处理
        int len = strs.length;
        // -统计
        int[][] statistics = new int[len][2];
        for(int i = 0; i < len; i++) {
            statistics[i][0] = Solution.count(strs[i], '0');
            statistics[i][1] = strs[i].length() - statistics[i][0];
        }
        // 2 创建dp表
        int[][][] dp = new int[len+1][m+1][n+1];
        // 3 初始化
        // 4 填表
        for(int i = 1; i <= len; i++) {
            for(int j = 0; j <= m; j++) {
                for(int k = 0; k <= n; k++) {
                    dp[i][j][k] = dp[i-1][j][k];
                    // -选
                    if(j >= statistics[i-1][0] && k >= statistics[i-1][1]) {
                        dp[i][j][k] = Math.max(dp[i][j][k], dp[i-1][j-statistics[i-1][0]][k-statistics[i-1][1]] + 1);
                    }
                }
            }
        }
        // 5 返回值
        return dp[len][m][n];
    }

    public static int count(String s, char t) {
        /**
         * 用于计算一个字符串中，指定字符出现的个数
         * @return 指定字符的个数
         * */
        int ret = 0;
        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == t) {
                ret ++;
            }
        }
        return ret;
    }
}
